
//123.买卖股票的最佳时机III
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 只能进行两次交易
        // 因为有交易限制,所以在使用DP表的时候要将交易的次数也考虑进去
        // 所以要不能再使用一维DP表了,可以使用一个二维DP表
        // 依旧是f表示有票,g表示没票

        const int INF = -0x3f3f3f3f;        //表示最小值

        int n = prices.size();
        vector<vector<int>> f(n,vector<int>(3,INF));
        auto g = f;
        f[0][0] = -prices[0] , g[0][0] = 0;
        for(int i = 1; i < n ;i++)
        {
            for(int j = 0 ;j < 3;j++)
            {
                f[i][j] = max(f[i-1][j] ,g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j - 1 >= 0) g[i][j] = max(g[i][j] , f[i-1][j-1] + prices[i]);
            }
        }
        return ranges::max(g[n-1]);
    }
};